Many hardware designs, such as memory sub-systems, contain resources that can receive more requests in a particular clock cycle than can be executed in a clock cycle. For example, a memory cache may have four requestors simultaneously requesting access to the cache, but the cache may only be able to execute or process one request per clock cycle. In these cases an arbitration scheme is required to determine the order in which the requests will be processed. In many cases the arbitration is done based on priorities assigned to the requestors so that requests from higher priority requestors are granted before requests from lower priority requestors. However, other arbitration schemes may also be used to prioritize the requestors and/or requests according to a specified arbitration policy.
Before a design is implemented in silicon the design is verified. This includes verifying that the design correctly implements the arbitration—i.e. prioritizes the requests according to the specified arbitration policy. Typically arbitration schemes are verified using dynamic simulation-based verification which involves applying input stimuli to the design implementation and comparing the output to a known reference output. However, dynamic simulation-based verification becomes difficult as the number of requestors grows since the number of cases and possible arbitration combinations becomes too large to test exhaustively.
The problem is exacerbated when requests can arrive both serially and concurrently. For example, a memory cache that is able to process only one request per clock cycle may receive two requests in a first clock cycle and then another two requests in a second clock cycle. The cache will not have processed both of the initial two requests before it receives the subsequent two requests. Accordingly, the arbitration scheme must implement a form of first-come-first-served selection in addition to priority selection. Exhaustively verifying that the arbitration is correct with respect to both selection parameters using dynamic simulation-based verification becomes an intractable task for a system with only a dozen requestors.
The embodiments described below are provided by way of example only and are not limiting of implementations which solve any or all of the disadvantages of known arbitration verification systems.